% 前面的初始化操作和模拟退火相同：初始化距离矩阵和随机数发生器

% w为种群的个数，g为进化代数
w = 50; g = 100;

% 改良圈算法
for k = 1:w
    c = randperm(100);
    c1 = [1,c+1, 1-2]; %生成初始解
    % 开始改良
    for t = 1:102  
        flag = 0;  % 退出改良圈循环的判断标准
        % 简单的二维数组遍历
        for m = 1:100 
            for n = m+2:101
                if d(c1(m), c1(n)) + d(c1(m+1), c1(n+1)) < d(c1(m),c1(m+1)) + d(c1(n), c1(n+1)) % 路径长度比较
                    c1(m+1:n) = c1(n:-1:m+1);
                    flag = 1;
                end
            end
        end
        if flag == 0
            J(k,c1) = 1:102; % 记录较好的解
            break;
        end
    end
end

J(:,1) = 0; J = J/102; % 把整数序列替换成实数（染色体编码）

% 遗传算法
for k = 1:g
    A = J;  % 子代A的染色体
    % 交叉操作
    c = randperm(w);  % 交叉的染色体对
    for i = 1:2:w
        F = 2 + floor(100 * rand(1));
        temp = A(c(i), [F:102]);
        A(c(i), [F:102]) = A(c(i+1), [F:102]);
        A(c(i+1), F:102) = temp;
    end
    % 变异操作
    % 随机选取产生变异的地址，并用by记录位置
    by = [];
    while ~length(by)
        by = find(rand(1,w) < 0.1); 
    end
    % 对产生变异的染色体进行位置交换处理
    B = A(by, :);
    for j = 1:length(by)
        bw = sort(2 + floor(100*rand(1,3)));
        B(j,:) = B(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:1-2]) % 交换位置
    end
    % 父代和子代种群合在一起
    G = [J; A; B];
    % 把染色体翻译成 1,..., 102的序列（ind1）
    [SG, ind1] = sort(G,2); 
    % 路径长度初始值
    num = size(G,1); long = zeros(1,num);
    for j = 1:num
        for i = 1:101
            long(j) = long(j) + d(ind1(j,i), ind1(j,i+1)); % 计算每条路径的长度
        end
    end
    % 选择操作
    % 对路径长度从小到大排序
    [slong, ind2] = sort(long); 
    % 选择前w个较短路径对应的染色体
    J = G(ind2(1:w), :); 
end

path = ind1(ind2(1),:), flong = slong(1); % 解的路径和长度

xx = sj(path,1); yy = sj(path,2);
plot(xx,yy,'-o');  % 画出路径
